//
// Created by hay boy on 2022/7/3.
//

#ifndef ALGORITHMS_MAZE_H
#define ALGORITHMS_MAZE_H

#include "../stack/ArrayStack.h"

class position{
public:
    int row,col;
    position(){
        row = col = 0;
    }
    position(int row,int col){
        this->row = row;
        this->col = col;
    }
    ~position(){
        row = col = 0;//为调试时专用，实际上没什么用
    }
};
//作用:可用于生成 可通过的 迷宫地图
bool findPath1(){
    auto path = new ArrayStack<position>;
    position offset[4];
    int size = 10;//size = 出口列标，为方形迷宫，行数=列数
    offset[0].row = 0;offset[0].col = 1;
    offset[1].row = 1;offset[1].col = 0;
    offset[2].row = 0;offset[2].col = -1;
    offset[3].row = -1;offset[3].col = 0;
    auto maze = new int*[size];
    for(int i = 0;i<size;i++){
        maze[i] = new int[size];
    }
    for(int i = 0;i<=size+1;i++){
        maze[0][i] = maze[size+1][i] = 1;
        maze[i][0] = maze[i][size+1] = 1;
    }
    position here;
    here.row = 1;
    here.col = 1;
    maze[1][1] = 1;
    int option = 0;
    int lastOption = 3;

    while(here.row!=size||here.col!=size){
        int r,c;
        while(option<=lastOption){
            r = here.row+offset[option].row;
            c = here.col+offset[option].col;
            if(maze[r][c]==0){
                break;
            }
            option++;
        }
        if(option<=lastOption){
            path->push(here);
            here.row = r;
            here.col = c;
            maze[r][c] = 1;
            option = 0;
        }else{
            if(path->empty()){
                return false;
            }
            position next = path->top();
            path->pop();
            if(next.row == here.row){
                option = 2 + next.col-here.col;
            }else{
                option = 3+next.row-here.row;
            }
            here = next;
        }
    }
    return true;
}
#endif //ALGORITHMS_MAZE_H
